In digital photography of single pictures, i.e. motionless still pictures, there is the problem that the required data quantities are very large. This particularly applies when the resolution in digital photography is to approximate that of chemical photography. A known standard for data compression of still pictures is the JPEG standard. This standard does not achieve sufficiently large data reduction rates and, moreover, has the drawback that a data reduction in fixed picture blocks of, for example, 8xc3x978 pixels is performed, which in the case of strong compression can be recognized as artefacts in the reconstructed picture.
To achieve higher compression rates, the Discrete Wavelet Transformation, referred hereinafter as DWT, is known. It has proved to be an efficient method in picture coding and compression. In wavelet transformation of the picture data, so-called wavelet coefficients or sub-bands are generated which can be subsequently quantized and entropy-encoded. The resultant compressed data stream may be used for transmission or storage. The DWT is the basis for future compression standards such as, for example, JPEG 2000 and is an alternative to the known Discrete Cosine Transform (DCT). In picture processing, the so-called two-dimensional Discrete Wavelet Transformation, hereinafter referred to as 2-D DWT, is used. This may be understood to be a consecutive application of a one-dimensional wavelet transformation in the horizontal and vertical directions.
The following aspects are essentially known from the state of the art.
On the one hand, the 2-D DWT can be performed by way of a complete, twice consecutive application of a simple DWT in the horizontal and vertical directions. However, the result is the necessity of buffering the data of the sub-bands between the first and the second transformation stage; thus a considerable memory volume is required. Furthermore, the bus load to and from which the data are copied is increased by at least a factor of 2.
Moreover, it is possible to perform a direct 2-D DWT in which the transformation is performed in one step. It is true that the bus load is reduced thereby but this poses the problem that a comparatively large part of the picture must be simultaneously available for transformation, so that it must be internally stored when it is being processed. In the state of the art, line memories or other memories are used for this purpose. This involves the problem that the size of the internal buffer memories borders on the maximum picture resolution to be processed and that these buffer memories are required as additional memories.
When the transformation is performed in a multiple, iterative way, in which the single sub-bands determined in a transformation operation are buffered time and again, the required memory volume for the initial picture is increased by approximately one-fourth. The sub-pictures are then rewritten into the picture memory. The picture memory must then, however, be implemented for the higher bit depth. Since only picture data, which are no longer necessary for further transformations, can be overwritten when the sub-pictures are being rewritten into the picture memory, the sub-pictures can be stored in the memory in a strongly fragmented form only. A possible subsequent re-assortment considerably increases the bus load, the memory space required for buffering and the computation time.
It is an object of the invention to provide an arrangement for transforming picture data which is suitable for the two-dimensional Discrete Wavelet Transformation and generates a minimum load of the memory bus, minimizing the overall required memory space, while the resolution of the picture to be processed is not limited by internal register sizes and its architecture provides a transformation without any losses.
According to the invention, this object is solved in that a picture memory is provided in which the data of a picture are stored prior to the start of the first transformation plane and in which the data of a further sub-band to be transformed are stored after the first transformation plane, in which process the data of the picture are partially overwritten, in that the data of a possible further sub-band to be segmented are stored in the picture memory after every further transformation plane, in that a sub-band memory is provided in which, after a transformation process of a plane, the data gained during this transformation of those sub-bands which are no longer to be segmented in further transformation planes are stored, which data of said sub-band are stored adjacent to each other and in which sub-band data determined in previous transformation planes and possibly already stored in the sub-band memory are not overwritten, in that, in the transformation planes, the data of the picture or the sub-band data stored in the last transformation plane are read from the picture memory, which data are read in blocks comprising a basic block having a size corresponding to the picture section or sub-band to be transformed, and a frame surrounding said picture section and having a width corresponding to half the maximum filter depth of the filters used for the transformation, and in that all basic blocks combined cover all pixels of the picture or sub-band data in the picture memory.
In the arrangement according to the invention, two memories are provided, namely one picture memory and one sub-band memory. The picture memory is provided to take up picture data of the picture to be transformed before the start of the first transformation plane. In every subsequent transformation plane, the sub-band to be further transformed is written into this picture memory. Since the original picture and the sub-band data stored in the picture memory during the previous transformation planes are no longer required for the subsequent transformation planes, the data of the picture or the data of the sub-band of the previous transformation plane can be overwritten. Thus, this picture memory can be dimensioned in such a way that, as far as its size is concerned, it is adequately dimensioned for taking up the original picture data. Consequently, no additional storage quantity is required in the picture memory for those data, to be stored in each transformation plane, of that sub-band which is to be further transformed.
After each transformation process of a plane, the data, gained during this transformation, of those sub-bands which are not to be subjected to a further transformation are stored in the sub-band memory. The data can then be stored adjacent to each other and can be stored in an ordered way or in the desired way in the sub-band memory so that no reassortment is required prior to reading the sub-band data.
When the transformations are being performed in the relevant transformation planes, not all data of the picture or of the sub-band stored in the picture memory and to be further transformed are read from the picture memory, but these data are read in blocks only and the transformation is performed for data of these blocks. However, to ensure that this block structure does not influence the transformation process, i.e. no block structure or similar disturbances appear in the reconstructed picture, the blocks are formed in such a way that they comprise a basic block having a size corresponding to the part of the picture or the sub-band to be transformed. This basic block thus comprises that part of the picture or sub-band which is to be transformed. Additionally, this basic block is surrounded by a frame which comprises so many pixels towards all sides that it has the maximum half filtering depth of the filters used in the transformation process. It is thereby ensured that the transformation process which is applied to the entire block is performed in such a way that the transformation can be performed for the data of the basic block without any disturbing effects by the block. The transformation for the pixels in the basic blocks is thus not influenced at all by the block structure and is therefore ideal.
As a result, it is achieved that a transformation in blocks can be performed so that the internal storage quantity for the transformation process can be reduced, but that this transformation in blocks does not influence the actual transformation process and particularly that no disturbances or block structures are visible in the reconstructed picture.
It is achieved by means of the arrangement according to the invention that storage of data of the sub-bands is possible without any additional re-assortment of data and that there is no storage fragmentation. Only a minimal memory access with a minimum bus load is required. No additional buffer memory is required for the further sub-band to be transformed because it can be taken care of by the picture memory without having to enlarge this memory. Moreover, reading of the pictures to be processed is not limited by the sizes of internal registers because these are absent. Due to the block-wise transformation, it is true that memory space within the arrangement is saved but that no additional errors or artefacts are produced.
In accordance with an embodiment of the invention as defined in claim 2, the picture or sub-band to be transformed is segmented into the blocks within which the transformation is to be performed, such that the basic blocks are adjacent to each other. This is necessary because a valid transformation can only be performed for the data within the basic blocks. Furthermore, the blocks are arranged in a plurality of rows or scanning lines.
In the application of the arrangement for a two-dimensional Discrete Wavelet Transformation, hereinafter referred to as 2-D DWT, the arrangement is particularly advantageous because no additional storage space is required in the picture memory for restoring that LL sub-band which is to be further transformed, and because the other sub-bands of each transformation plane which are not further to be transformed can be stored in a sub-band memory in an orderly way.
As is characterized by a further embodiment as defined in claim 4, the picture memory and the sub-band memory may be advantageously built up in common. It is true that they can be maintained separately, because of the organization as described above, but they may advantageously be physically realized in one memory.
A further embodiment of the invention as defined in claim 5 provides the additional advantage that the sub-band data stored in a relevant transformation plane in the sub-band memory are retrievable from the sub-band memory already after termination of this transformation plane and before the start of the next transformation plane, so as to possibly further process these data.
The invention also relates to an arrangement for inverse transformation of picture data, particularly for inverse 2-D DWT as defined in claim 6. A similar structure as in the transformation arrangement according to the invention, defined in claim 1, is provided. There is also a sub-band memory and a picture memory, in which, before performing the inverse transformation, that sub-band of a picture to be retransformed is stored which was generated during the transformation as the last sub-band that was no longer to be transformed. Before performing the inverse transformation, all other sub-bands of the picture are stored in the sub-band memory. When the inverse transformation is being performed, the sub-bands stored in the sub-band memory are added, in the predetermined sequence and possibly using scaling factors, to the sub-band stored in the picture memory. The addition result generated in every new inverse transformation plane is written into the picture memory again so that data previously stored in this memory are overwritten.
The structure of the two memories in the arrangement thus also proves to be advantageous for an arrangement for inverse transformation.
These and other aspects of the invention are apparent from and will be elucidated with reference to the embodiments described hereinafter.